Today’s Agenda

  • Hausdorff Distance
  • Gromov–Hausdorff Distance
  • Hasudorff vs Gromov–Hausdorff
  • The curious case of the circle
  • Lower bounds
    • Riemannian manifolds
    • metric graphs
  • Future work

The Hausdorff Distance

Definition 1 (Directed Hausdorff Distance) For two subsets compact \(X,Y\subset\mathbb R^n\), their Hausdorff distance is \[ \vec{d}_H(X,Y)=\min\bigg\{r\geq0\mid X\subset \bigcup_{y\in Y} B(y,r)\bigg\}. \]

Definition 2 (Hausdorff Distance) \[ d_H(X,Y)=\max\bigg\{\vec{d}_H(X,Y),\vec{d}_H(Y,X)\bigg\}. \]

A Little Demo

Why Only Euclidean Subsets?

Definition 3 (Hausdorff Distance) Let \((Z,d)\) be a metric space and \(X, Y\subset Z\) compact subsets. \[ \vec{d}^Z_H(X,Y)=\min\{r\geq0\mid X\subset \cup_{y\in Y} B(y,r)\}. \]

\[ d^Z_H(X,Y)=\max\bigg\{\vec{d}^Z_H(X,Y),\vec{d}^Z_H(Y,X)\bigg\}. \]

The Circle

\(Z=S^1\) is the circle with circumference \(2\pi\)

\[ d_H(X,S^1)=\frac{\pi}{4}. \]

The Gromov–Hausdorff Distance

What if the subsets \(X,Y\) have no common embeddding?

Isometric embedding

\[ d_{GH}(X,Y)=\inf d^Z_H(f(X),g(Y)) \]

Some Properties and Results

  • \(d_{GH}(X,Y)=0\) if and only if \(X\), \(Y\) are isometric

  • \[\tfrac{1}{2}|diam(X)-diam(Y)|\leq d_{GH}(X,Y)\leq \tfrac{1}{2}\max\big\{diam(X), diam(Y)\big\}\]

  • When \(X, Y\) are finite metric spaces

    • Computationally feasible (distortion definition)
    • Minimization problem with exponential search space

  • If \(X,Y\) metric graphs, then \(NP\)-hard (A. Aggarawal et al.)

  • If \(X,Y\subset\mathbb{R}^1\), then \(\frac{5}{4}\)-approximable (Majhi et al.)

Hausdorff vs Gromov–Hausdorff

  • Let \((Z,d)\) be a metric space and \(X\subset Z\)
    • \(d_H(X,Z)\) is well-defined
  • \((X,d)\) is also a metric space
    • \(d_{GH}(X,Z)\) can be defined

How the two distances \(d_{GH}(X,Z)\) and \(d^Z_H(X,Z)\) compare?

  • \(d_{GH}(X,Z)\color{green}{\leq} d_H(X,Z)\)

  • \(d_{GH}(X,Z) \color{red}{=} d_H(X,Z)\)?

Comparison on the Circle

\[ d_H(X,S^1)=\frac{\pi}{2} \]

\[ \frac{1}{2}\pi\leq d_{GH}(X,S^1)\leq \frac{1}{2}\pi \implies d_{GH}(X,S^1)=\frac{\pi}{2} \]

Comparison on the Circle

\[ d_H(X,S^1)=\frac{\pi}{4} \]

\[ \frac{1}{2}0\leq d_{GH}(X,S^1)\leq \frac{1}{2}\pi \implies ? \]

\(d_{GH}(X,S^1)=d_H(X,S^1)\)

Comparison on the Circle

\[ \frac{\pi}{3}=d_{GH}(X,S^1)<d_{H}(X,S^1)=\frac{\pi}{3}+\varepsilon. \]

Optimal Density for the Circle

Theorem 1 (2023) For \(X\subset S^1\) with \(d_H(X,S^1)<\frac{\pi}{6}\), then \(d_{GH}(X,S^1)=d_H(X,S^1)\).

  • Proof is topological
  • Is \(\frac{\pi}{6}\) optimal?

Theorem 2 (2024) For \(X\subset S^1\) with \(d_H(X,S^1)<\frac{\pi}{3}\), then \(d_{GH}(X,S^1)=d_H(X,S^1)\).

  • Proof is purely geometric

Another Perspective

  • \(d_{GH}(X,S^1)\geq\min\big\{d_H(X, S^1),\frac{\pi}{3}\big\}\).

Corollary 1 (Two Subsets) For \(X,Y\subset S^1\) with \(d_H(Y,S^1)\leq\varepsilon\), then \[d_{GH}(X,Y)\geq\min\big\{d_H(X, Y)-2\varepsilon,\tfrac{\pi}{3}-\varepsilon\big\}.\]

  • \(O(n^2)\) lower-bound for \(\max{|X|, |Y|}=n\).

Non-Trivial Lower Bounds

  • Intuition: when a sample becomes dense enough, it starts to capture the geometry of the space.

  • Generally: \(d_{GH}(X,Z)\geq\min\big\{\color{red}{C}\cdot d_H(X, Z), \color{red}{D}\big\}\)?

    • Cirlce: \(C=1\) and \(D=\frac{\pi}{3}\).

Theorem 3 (Bad News) For any \(C>0\), there exists a compact metric space \(Z\) and a subset \(X\subseteq Z\) with \(d_{GH}(X,Z) < C \cdot d_{H}(X,Z).\)

Good News

Theorem 4 (Closed Riemannian Manifolds) For \(X\subset M\), we have \[ d_{GH}(X,M)\geq\min\bigg\{\color{green}{\frac{1}{2}}d_H(X, S^1),\color{green}{\frac{\rho}{6}}\bigg\}. \]

  • \(\rho\) is the convexity radius of \(M\)
  • \(C=\frac{1}{2}\) can be improved using Jung’s theorem

Metric Trees and Graphs

Theorem 5 (Trees) Let \(T\) be a compact tree with finite edges. For any \(X\subset T\) so that \(d_H(T,X)<\vec{d}_H(\delta T, X)\), we have \[ d_{GH}(X,T)=d_H(X, T). \]

Theorem 6 (Graphs) Let \(G\) be a compact tree with finite edges. For any \(X\subset G\) so that \(d_H(G,X)<\vec{d}_H(\delta G, X)\), we have \[ d_{GH}(X,G)\geq\min\bigg\{{d_H(X, S^1),\tfrac{e(G)}{12}}\bigg\}. \]

  • \(e(G)\) denotes the length of the shortest edge.

Questions

  • For metric graphs, is the density constant \(\frac{e(G)}{12}\) optimal?

    • We conjecture that \(\frac{e(G)}{8}\) should suffice.

  • What about Riemannian manifolds with bounday?

  • Are there classes of metric spaces—like the circle, metric graphs—so that \(C=1\)?

Thank you